package com.example.algorithm.Math;

// 本例演示的是：求两个数的最大公约数
// 求两个数的最大公约数，本例中使用的是辗转相除法。
//
// 什么是辗转相除法：辗转相除法的思想是，通过反复用较小数去除较大数，然后用余数替换较大数，直到其中一个数变为 0，此时另一个数即为两数的最大公约数。
//
// 为什么使用辗转相除法能求两个数的最大公约数：
// 辗转相除法（欧几里德算法）能够求出两个数的最大公约数的原因在于其基于以下数学原理：
// 公约数性质： 如果一个数能同时整除两个数，那么它也一定能够整除它们的差值。
// 最大公约数定义： 两个数的最大公约数是能够同时整除它们的最大正整数。
public class GCD {

    // 求a和b的最大公约数
    public static int gcd(int a, int b) {
        // 如果其中一个数为 0，则另一个数即为最大公约数
        if (b == 0) {
            return a;
        }
        // 递归调用 gcd 方法，直到 b 为 0
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        int num1 = 24;
        int num2 = 36;
        System.out.println("GCD of " + num1 + " and " + num2 + " is: " + gcd(num1, num2));
    }
}

